﻿using System;
using System.Collections.Generic;

namespace QSharp.Scheme.Utility.HBSpaceMgmt
{
    using Classical.Trees;

    public class BTreeSection : Section, ISection, IBTreeSection, BTree.INodeCreator<Node, Hole>
    {
        /**
         * <summary>
         *  Section layout
         *   Position of root
         *   Node1 (not guaranteed to be root)
         *   Node2
         *   ... there may be holes intermittantly
         * </summary>
         */

        public ISection Superior = null;        /* superior section that governs this */

        public readonly IStream SectionStream;  /* underlying stream for this section */

        public readonly INodeEncoder NodeEncoder;
        public readonly NodeCache Cache;
        public readonly int BTreeOrder;

        /* this is needed by the root section when updating b-tree roots to its stream */
        public IPosition RootPosition = null;

        public Queue<IPosition> DeletedNodePages = new Queue<IPosition>();

        public static ISize GetLeastNodePageSize(IOperator op, INodeEncoder nodeEncoder, 
            IChunkDescriptorEncoder lumpHeaderEncoder, IChunkDescriptorEncoder lumpFooterEncoder)
        {
            ISize size;
            if (op != null)
            {
                size = op.Add(nodeEncoder.EncodedSize, lumpHeaderEncoder.EncodedSize);
                size = op.Add(size, lumpFooterEncoder.EncodedSize);
            }
            else
            {
                size = nodeEncoder.EncodedSize;
                size = size.Add(lumpHeaderEncoder.EncodedSize);
                size = size.Add(lumpFooterEncoder.EncodedSize);
            }
            return size;
        }

        /**
         * <remarks>
         *  `targetStart' starts from the first chunk of the target stream to accommodate a node
         * </remarks>
         */
        public BTreeSection(IStream sectionStream, INodeEncoder nodeEncoder, int btreeOrder)
        {
            SectionStream = sectionStream;

            NodeEncoder = nodeEncoder;
            Cache = new NodeCache(sectionStream, this,
                nodeEncoder, new Node.DisposedDelegate(Disposed));

            BTreeOrder = btreeOrder;
        }


        /* Implementation for ISection */

        /**
         * <remarks>
         *  Section encoding/decoding deals with header
         *  only, since cache's life cycle is restricted
         *  in a single transaction (e.g. Allocate or
         *  Deallocate), from loading its first (root)
         *  node to closing the cache.
         * </remarks>
         */
        public void Encode()
        {
            // nothing to encode on the section level
        }

        public void Decode()
        {
            // nothing to decoded on the section level
        }


        /**
         * <summary>
         *  Part of resetting the entire management system
         * </summary>
         */
        public void Reset()
        {
            IPosition start = TargetStart;
            ISize size = TargetSize;

            BTreeSection inferiorSection = Inferior as BTreeSection;
            if (inferiorSection == null)
            {
                IPosition uPos = TargetPaginator.Unpaginate(start, TargetPageSize);
                TargetStream.Position = uPos;
                base.HoleHeaderEncoder.ChunkSize = size;
                base.HoleHeaderEncoder.Encode(TargetStream);

                uPos = TargetPaginator.Unpaginate(TargetPaginator.Add(start, size), TargetPageSize);
                uPos = TargetPaginator.Subtract(uPos, base.HoleFooterEncoder.EncodedSize);
                TargetStream.Position = uPos;
                base.HoleFooterEncoder.ChunkSize = size;
                base.HoleFooterEncoder.Encode(TargetStream);
            }
            else
            {
                /**
                 * <remarks>
                 *  the target stream contains one used chunk (root) initially
                 * </remarks>
                 */
                start = TargetPaginator.Add(start, TargetPaginator.OnePage);
                size = TargetPaginator.Subtract(size, TargetPaginator.OnePage);
            }

            Section superior = Superior as Section;
            System.Diagnostics.Trace.Assert(superior != null);

            IPosition sectionStart = Superior.TargetStart;
            ISize sectionSize = Superior.TargetSize;

            IOperator op = Superior.TargetOperator;
            IPaginator paginator = Superior.TargetPaginator;
            ISize pageSize = Superior.TargetPageSize;
            ISize oneNodePage = paginator.OnePage;

            /* Encode the stream container */
            IPosition destPos = paginator.Unpaginate(sectionStart, pageSize);
            SectionStream.Position = destPos;
            superior.LumpHeaderEncoder.ChunkSize = oneNodePage;
            superior.LumpHeaderEncoder.Encode(SectionStream);

            destPos = op.Add(destPos, pageSize);
            destPos = op.Subtract(destPos, superior.LumpFooterEncoder.EncodedSize);
            SectionStream.Position = destPos;
            superior.LumpFooterEncoder.ChunkSize = oneNodePage;
            superior.LumpFooterEncoder.Encode(SectionStream);

            ISize holeSize = paginator.Subtract(sectionSize, oneNodePage);
            destPos = destPos.Add(superior.LumpFooterEncoder.EncodedSize);
            SectionStream.Position = destPos;
            superior.HoleHeaderEncoder.ChunkSize = holeSize;
            superior.HoleHeaderEncoder.Encode(SectionStream);

            destPos = paginator.Add(sectionStart, sectionSize);
            destPos = paginator.Unpaginate(destPos, pageSize);
            destPos = op.Subtract(destPos, superior.HoleFooterEncoder.EncodedSize);
            SectionStream.Position = destPos;
            superior.HoleFooterEncoder.ChunkSize = holeSize;
            superior.HoleFooterEncoder.Encode(SectionStream);

            /* Encode the header */
            RootPosition = sectionStart;

            /* Encode the root node */
            Node node = Node.CreateRoot(Cache, RootPosition, new Hole(start, size));
            destPos = paginator.Unpaginate(sectionStart, pageSize);
            destPos = op.Add(destPos, superior.LumpHeaderEncoder.EncodedSize);
            SectionStream.Position = destPos;
            NodeEncoder.Encode(node, SectionStream);
        }

        /**
         * <summary>
         *  Search in the current B-tree section for a hole that can 
         *  accommmodate an allocation of size `size'
         *  The hole's position is given by `node' and `index'
         * </summary>
         */
        protected bool Search(Node root, ISize size, out Node node, out int index)
        {
            Hole hole = new Hole(TargetStart, size);
            BTree.BinarySearch<Node, Hole>(root, hole, out node, out index);

            if (index >= node.EntryCount)
            {
                index--;
                BTree.GotoNextInorder<Node, Hole>(ref node, ref index);

                if (node != null)
                    return true;

                return false;   // no accommodation
            }

            return true;
        }

        public List<IPosition> AllocateForNodes(ISize size)
        {
            Node root = Cache.LoadNode(RootPosition);

            List<IPosition> posList = new List<IPosition>();

            bool runLoop = true;
            while (runLoop)
            {
                Node node;
                int index;
                Hole hole, newHole;
                IPosition nodePos, nodePosEnd;

                if (root == null)
                {
                    throw new ApplicationException("Unexpected node page allocation failure");
                }

                bool allocableWithChunk = Search(root, size, out node, out index);
                if (allocableWithChunk)
                {
                    hole = node.GetEntry(index);

                    BTree.Remove<Node, Hole>(node, index, BTreeOrder, ref root);
                    base.AllocatePages(hole, size, out newHole);

                    if (newHole != null)
                    {
                        BTree.BinarySearch<Node, Hole>(root, newHole, out node, out index);
                        BTree.Insert<Node, Hole>(newHole, node, index, BTreeOrder, ref root, this);
                    }

                    runLoop = false;
                }
                else
                {
                    node = root;
                    BTree.GotoLastInorder<Node, Hole>(ref node, out index);
                    hole = node.GetEntry(index);

                    BTree.Remove<Node, Hole>(node, index, BTreeOrder, ref root);
                    base.AllocatePages(hole, hole.Size, out newHole);

                    System.Diagnostics.Trace.Assert(newHole == null);

                    size = TargetPaginator.Subtract(size, hole.Size);    // update remaining size
                }

                nodePos = hole.Start;
                nodePosEnd = TargetPaginator.Add(hole.Start, size);
                while (nodePos.CompareTo(nodePosEnd) < 0)
                {
                    posList.Add(nodePos);
                    nodePos = TargetPaginator.Add(nodePos, TargetPaginator.OnePage);
                }
            }

            FinalizeTransaction();

            RootPosition = root.PosCurrent; // update root's page position

            Cache.Close();

            return posList;
        }

        /**
         * <summary>
         *  both `size' and the return value are paginated
         * </summary>
         */
        public IPosition Allocate(ISize size)
        {
            Node root = Cache.LoadNode(RootPosition);

            Node node;
            int index;

            bool allocable = Search(root, size, out node, out index);

            if (!allocable)
                return null;

            Hole hole = node.GetEntry(index);

            BTree.Remove<Node, Hole>(node, index, BTreeOrder, ref root);

            Hole newHole;
            base.Allocate(hole, size, out newHole);

            if (newHole != null)
            {
                BTree.BinarySearch<Node, Hole>(root, newHole, out node, out index);

                BTree.Insert<Node, Hole>(newHole, node, index, BTreeOrder, ref root, this);
            }

            FinalizeTransaction();

            if (root != null)
                RootPosition = root.PosCurrent; // update root's page position
            else
                RootPosition = null;
            
            Cache.Close();

            return hole.Start;
        }

        /**
         * <summary>
         *  `destPos' is paginated
         * </summary>
         */
        public void Deallocate(IPosition pos)
        {
            bool found;
            Hole oldHole1, oldHole2;
            Hole newHole;

            Node root = RootPosition != null ? Cache.LoadNode(RootPosition) : null;
            Node node;
            int index;

            base.Deallocate(pos, out oldHole1, out oldHole2, out newHole);

            if (oldHole1 != null)
            {
                found = BTree.BinarySearch<Node, Hole>(root, oldHole1, out node, out index);
                if (!found)
                    throw new ApplicationException("Bad B-tree section");
                BTree.Remove<Node, Hole>(node, index, BTreeOrder, ref root);
            }

            if (oldHole2 != null)
            {
                found = BTree.BinarySearch<Node, Hole>(root, oldHole2, out node, out index);
                if (!found)
                    throw new ApplicationException("Bad B-tree section");
                BTree.Remove<Node, Hole>(node, index, BTreeOrder, ref root);
            }

            found  = BTree.BinarySearch<Node, Hole>(root, newHole, out node, out index);
            if (found)
                throw new ApplicationException("Bad B-tree section");

            BTree.Insert<Node, Hole>(newHole, node, index, BTreeOrder, ref root, this);

            FinalizeTransaction();

            RootPosition = root.PosCurrent; // update root's page position
            
            Cache.Close();
        }

        /* Implementation for BTree.INodeCreator<Node, Hole> */
        public Node Create()
        {
            /**
             * <remarks>
             *  this is the paginated position
             * </remarks>
             */
            return Cache.CreateNode();
        }

        public void Disposed(Node sender)
        {
            /**
             * <remarks>
             *  this is the paginated position
             * </remarks>
             */
            IPosition nodePos = sender.PosCurrent;

            DeletedNodePages.Enqueue(nodePos);
        }

        public void FinalizeTransaction()
        {
            int i;
            for (i = 0; i < Cache.CachedNodes.Count; i++)
            {
                Node node = Cache.CachedNodes[i];
                if (node == null || node.PosCurrent != null)
                    continue;

                if (DeletedNodePages.Count > 0)
                {
                    IPosition pos = DeletedNodePages.Dequeue();
                    node.SetNodePosition(pos);
                }
                else
                    break;
            }

            if (DeletedNodePages.Count > 0)
            {
                IPosition pos = DeletedNodePages.Dequeue();
                Superior.Deallocate(pos);
            }
            else
            {
                ISize sizeNeeded = null;
                int iStart = i;
                for (; i < Cache.CachedNodes.Count; i++)
                {
                    Node node = Cache.CachedNodes[i];
                    if (node == null || node.PosCurrent != null)
                        continue;

                    if (sizeNeeded == null)
                        sizeNeeded = Superior.TargetPaginator.OnePage;
                    else
                        sizeNeeded = Superior.TargetPaginator.Add(sizeNeeded,
                            Superior.TargetPaginator.OnePage);
                }

                if (sizeNeeded != null)
                {
                    List<IPosition> posList = Superior.AllocateForNodes(sizeNeeded);
                    int j = 0;
                    for (i = iStart; i < Cache.CachedNodes.Count; i++)
                    {
                        Node node = Cache.CachedNodes[i];
                        if (node == null || node.PosCurrent != null)
                            continue;

                        node.SetNodePosition(posList[j]);
                        j++;
                    }
                }
            }
        }

        /* Implementation for IBtreeSection, beginning of */

        public IPosition NodePaginate(IPosition pos)
        {
            pos = Superior.TargetOperator.Subtract(pos, base.LumpFooterEncoder.EncodedSize);
            pos = Superior.TargetPaginator.Paginate(pos, Superior.TargetPageSize);
            return pos;
        }

        public IPosition NodeUnpaginate(IPosition pos)
        {
            pos = Superior.TargetPaginator.Unpaginate(pos, Superior.TargetPageSize);
            pos = Superior.TargetOperator.Add(pos, base.LumpFooterEncoder.EncodedSize);
            return pos;
        }

        /* Implementation for IBtreeSection, end of */
    }
}
